
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

/**
 * 给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串（重复字符算做不同字符）。
 * <p>
 * 示例：
 * <p>
 * 输入: S = "ADOBECODEBANC", T = "ABC"
 * 输出: "BANC"
 * 说明：
 * <p>
 * 如果 S 中不存这样的子串，则返回空字符串 ""。
 * 如果 S 中存在这样的子串，我们保证它是唯一的答案。
 */
class Solution {

    public static void main(String[] args) {
        System.out.println(minWindow("ADOBECODEBANC", "ABC"));
        //System.out.println(minWindow("cabwefgewcwaefgcf", "cae"));
        //System.out.println(minWindow("ezsevejszgvxqqggbwkxpwzoyrbaslnxmfdjmmentzllptsspeshatvbkwbcjozwwcfirjxmiixadrsvwmcyfzzpxauhptdlyivrssdadacisxdojhopgogeoalfwoswypnqiqtnqxvkubaeiptpdzvtaizywtuwjhptxkgnhdaceagppbeuabocjpahiudrdskacsqmwqocqurivxcxyqcjfcqqzwheqsfvkxhinvlfrenmcslcinoqsggtcpxtjcowbveosrwjyjvcbigmwueobmjdbgynlojmjpbbjzmhkjjosraomgepsnuvvtkghtttlwwuxjdhsovmfvctdiixxdvtyfzhbuamszipklxezsrgqtavcitzloulvwtwqvklwscgfznguenmzphdxcdlqxwotrkmnxzjrbsxdffxlslkhsohxtupsqdokqaxnzieccdfhjesdpfnktuhoqwgicussurhvalaerfmakgfznslioswerdntxfnuxurzhrfyzrajagkpywypqutjzicxqrtplkqtevtdpuoraagayeppblyavdzluscifsblowqdqeuqectdjkukxumtzogwijenbhapdquuwqmbthgcscmpyaiyorwxaambjntmfnicexfzenbyppoppyngpjdplrtugojmbtqhsvixkjxbylqqmgwbpbtdsozzcinfedpwaxvkhtnhgdxsjtwburephdojodouifqkdowmjjtpmrkwmizjzdygioryrhsznllqbhekqxbeqlcdtbougmcpavptdkuqvfiymmieljkcxnhsovpvjrmjnbcqlwiidsirgqvrcfvbuctlzigicutrxxjlvrvylerrwmkaugbqkxbkhjujdqcdplolejlpndimrtmnzoelnfvupsgukixzwlkaxysmbayuvliubogotdkkxqhhbejxsvxrtpdwsetnrb", "ksrsimxsxxjegkkpj"));
        //System.out.println(minWindow("a", "a"));
    }

    private static Map<Character, Integer> sMap = new HashMap();
    private static Map<Character, Integer> tMap = new HashMap();
    private static Map.Entry entry;
    private static Character key;
    private static Integer val;

    /**
     * 滑动窗口算法
     *
     * @param s
     * @param t
     * @return
     */
    public static String minWindow(String s, String t) {
        tMap.clear();
        sMap.clear();
        getMap(t);
        int start = 0, end = 0;
        int mark1 = 0, mark2 = 0;
        char[] chars = s.toCharArray();
        Character tmp = null;
        char endChar, c;
        boolean checked;
        int min = Integer.MAX_VALUE;
        for (; end < chars.length; ) {
            endChar = chars[end];
            if (!tMap.containsKey(endChar)) {
                end++;
                continue;
            }
            if (sMap.containsKey(endChar)) {
                sMap.put(endChar, sMap.get(endChar) + 1);
            } else {
                sMap.put(endChar, 1);
            }
            end++;
            if (null == tmp) {
                checked = check();
            } else {
                checked = tmp == endChar;
            }
            if (checked) {
                // 如果匹配到了
                for (; start < end; start++) {
                    c = chars[start];
                    if (tMap.containsKey(c)) {
                        if (sMap.get(c) - 1 < tMap.get(c)) {
                            // 尝试去掉i，直到不满足为止
                            tmp = c;
                            break;
                        } else {
                            sMap.put(c, sMap.get(c) - 1);
                        }
                    }
                }
                if (end - start < min) {
                    mark1 = start;
                    mark2 = end;
                    min = end - start;
                }
                // 尝试去掉一个
                start++;
                sMap.put(tmp, sMap.get(tmp) - 1);
            }
        }
        return s.substring(mark1, mark2);
    }

    private static void getMap(String t) {
        char c;
        for (int i = 0; i < t.length(); i++) {
            c = t.charAt(i);
            if (tMap.containsKey(c)) {
                tMap.put(c, tMap.get(c) + 1);
            } else {
                tMap.put(c, 1);
            }
        }
    }

    private static boolean check() {
        Iterator iterator = tMap.entrySet().iterator();
        while (iterator.hasNext()) {
            entry = (Map.Entry) iterator.next();
            if (sMap.getOrDefault((Character) entry.getKey(), 0) < (Integer) entry.getValue()) {
                return false;
            }
        }
        return true;
    }


}